
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-08-16
 * Time: 15:29
 */

/**
 * 给定一棵二叉树，已知其中的节点没有重复值，请判断该二叉树是否为搜索二叉树和完全二叉树。
 * 输出描述：分别输出是否为搜索二叉树、完全二叉树。
 *
 *
 * 数据范围：二叉树节点数满足
 * 0
 * ≤
 * n
 * ≤
 * 500000
 * 0≤n≤500000 ，二叉树上的值满足

 *
 * 注意：空子树我们认为同时符合搜索二叉树和完全二叉树。
 */
public class Judge {
    static class TreeNode{
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }

    }
    public boolean[] judgeIt (TreeNode root) {

        return new boolean[]{isSearch(root), isFull(root)};
    }

    public int num = 0;//每次递归会回要定义为成员变量
    public boolean isSearch(TreeNode root) {
        if(root == null) {
            return true;
        }

        boolean leftTree = isSearch(root.left);
        if(num > root.val) {
            return false;
        }

        num = root.val;

        boolean rightTree = isSearch(root.right);

        return leftTree && rightTree;
    }

    public boolean isFull(TreeNode root) {
        if(root == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean flg = false;
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur != null) {
                if(!flg){
                    queue.add(cur.left);
                    queue.add(cur.right);
                }else{
                    //第N次拿出来不是'null'
                    return false;
                }
            }else {
                flg = true; //flg = true时弹出的元素cur是空的
            }
        }
        //queue.isEmpty()返回true
        return true;
    }
}
